home *** CD-ROM | disk | FTP | other *** search
/ AGA Toolkit '97 / The AGA Toolkit '97.iso / miscellaneous / science / maths / calc / source / assocfunc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-09-07  |  10.7 KB  |  514 lines
  1. /*
  2.  * Copyright (c) 1994 David I. Bell
  3.  * Permission is granted to use, distribute, or modify this source,
  4.  * provided that this copyright notice remains intact.
  5.  *
  6.  * Association table routines.
  7.  * An association table is a type of value which can be "indexed" by
  8.  * one or more arbitrary values.  Each element in the table is thus an
  9.  * association between a particular set of index values and a result value.
  10.  * The elements in an association table are stored in a hash table for
  11.  * quick access.
  12.  */
  13.  
  14. #include "value.h"
  15.  
  16.  
  17. #define    MINHASHSIZE    31    /* minimum size of hash tables */
  18. #define    GROWHASHSIZE    50    /* approximate growth for hash tables */
  19. #define    CHAINLENGTH    10    /* desired number of elements on a hash chain */
  20. #define    ELEMSIZE(n)    (sizeof(ASSOCELEM) + (sizeof(VALUE) * ((n) - 1)))
  21.  
  22.  
  23. static ASSOCELEM *elemindex MATH_PROTO((ASSOC *ap, long index));
  24. static BOOL compareindices MATH_PROTO((VALUE *v1, VALUE *v2, long dim));
  25. static void resize MATH_PROTO((ASSOC *ap, long newsize));
  26. static void assoc_elemfree MATH_PROTO((ASSOCELEM *ep));
  27. static long nextprime MATH_PROTO((long n));
  28.  
  29.  
  30. /*
  31.  * Return the address of the value specified by normal indexing of
  32.  * an association.  The create flag is TRUE if a value is going to be
  33.  * assigned into the specified indexing location.  If create is FALSE and
  34.  * the index value doesn't exist, a pointer to a NULL value is returned.
  35.  */
  36. VALUE *
  37. associndex(ap, create, dim, indices)
  38.     ASSOC *ap;        /* association to index into */
  39.     BOOL create;        /* whether to create the index value */
  40.     long dim;        /* dimension of the indexing */
  41.     VALUE *indices;        /* table of values being indexed by */
  42. {
  43.     ASSOCELEM **listhead;
  44.     ASSOCELEM *ep;
  45.     static VALUE val;
  46.     HASH hash;
  47.     int i;
  48.  
  49.     if (dim <= 0)
  50.         math_error("No dimensions for indexing association");
  51.  
  52.     /*
  53.      * Calculate the hash value to use for this set of indices
  54.      * so that we can first select the correct hash chain, and
  55.      * also so we can quickly compare each element for a match.
  56.      */
  57.     hash = 0;
  58.     for (i = 0; i < dim; i++)
  59.         /* ignore Saber-C warning about Over/underflow */
  60.         hash = hash * 67319821 + hashvalue(&indices[i]);
  61.  
  62.     /*
  63.      * Search the correct hash chain for the specified set of indices.
  64.      * If found, return the address of the found element's value.
  65.      */
  66.     listhead = &ap->a_table[hash % ap->a_size];
  67.     for (ep = *listhead; ep; ep = ep->e_next) {
  68.         if ((ep->e_hash != hash) || (ep->e_dim != dim))
  69.             continue;
  70.         if (compareindices(ep->e_indices, indices, dim))
  71.             return &ep->e_value;
  72.     }
  73.  
  74.     /*
  75.      * The set of indices was not found.
  76.      * Either return a pointer to a NULL value for a read reference,
  77.      * or allocate a new element in the list for a write reference.
  78.      */
  79.     if (!create) {
  80.         val.v_type = V_NULL;
  81.         return &val;
  82.     }
  83.  
  84.     ep = (ASSOCELEM *) malloc(ELEMSIZE(dim));
  85.     if (ep == NULL)
  86.         math_error("Cannot allocate association element");
  87.     ep->e_dim = dim;
  88.     ep->e_hash = hash;
  89.     ep->e_value.v_type = V_NULL;
  90.     for (i = 0; i < dim; i++)
  91.         copyvalue(&indices[i], &ep->e_indices[i]);
  92.     ep->e_next = *listhead;
  93.     *listhead = ep;
  94.     ap->a_count++;
  95.  
  96.     resize(ap, ap->a_count / CHAINLENGTH);
  97.  
  98.     return &ep->e_value;
  99. }
  100.  
  101.  
  102. /*
  103.  * Search an association for the specified value starting at the
  104.  * specified index.  Returns the element number (zero based) of the
  105.  * found value, or -1 if the value was not found.
  106.  */
  107. long
  108. assocsearch(ap, vp, index)
  109.     ASSOC *ap;
  110.     VALUE *vp;
  111.     long index;
  112. {
  113.     ASSOCELEM *ep;
  114.  
  115.     if (index < 0)
  116.         index = 0;
  117.     while (TRUE) {
  118.         ep = elemindex(ap, index);
  119.         if (ep == NULL)
  120.             return -1;
  121.         if (!comparevalue(&ep->e_value, vp))
  122.             return index;
  123.         index++;
  124.     }
  125. }
  126.  
  127.  
  128. /*
  129.  * Search an association backwards for the specified value starting at the
  130.  * specified index.  Returns the element number (zero based) of the
  131.  * found value, or -1 if the value was not found.
  132.  */
  133. long
  134. assocrsearch(ap, vp, index)
  135.     ASSOC *ap;
  136.     VALUE *vp;
  137.     long index;
  138. {
  139.     ASSOCELEM *ep;
  140.  
  141.     if (index >= ap->a_count)
  142.         index = ap->a_count - 1;
  143.     while (TRUE) {
  144.         ep = elemindex(ap, index);
  145.         if (ep == NULL)
  146.             return -1;
  147.         if (!comparevalue(&ep->e_value, vp))
  148.             return index;
  149.         index--;
  150.     }
  151. }
  152.  
  153.  
  154. /*
  155.  * Return the address of an element of an association indexed by the
  156.  * double-bracket operation.
  157.  */
  158. static ASSOCELEM *
  159. elemindex(ap, index)
  160.     ASSOC *ap;        /* association to index into */
  161.     long index;        /* index of desired element */
  162. {
  163.     ASSOCELEM *ep;
  164.     int i;
  165.  
  166.     if ((index < 0) || (index > ap->a_count))
  167.         return NULL;
  168.  
  169.     /*
  170.      * This loop should be made more efficient by remembering
  171.      * previously requested locations within the association.
  172.      */
  173.     for (i = 0; i < ap->a_size; i++) {
  174.         for (ep = ap->a_table[i]; ep; ep = ep->e_next) {
  175.             if (index-- == 0)
  176.                 return ep;
  177.         }
  178.     }
  179.     return NULL;
  180. }
  181.  
  182.  
  183. /*
  184.  * Return the address of the value specified by double-bracket indexing
  185.  * of an association.  Returns NULL if there is no such element.
  186.  */
  187. VALUE *
  188. assocfindex(ap, index)
  189.     ASSOC *ap;        /* association to index into */
  190.     long index;        /* index of desired element */
  191. {
  192.     ASSOCELEM *ep;
  193.  
  194.     ep = elemindex(ap, index);
  195.     if (ep == NULL)
  196.         return NULL;
  197.     return &ep->e_value;
  198. }
  199.  
  200.  
  201. /*
  202.  * Compare two associations to see if they are identical.
  203.  * Returns TRUE if they are different.
  204.  */
  205. BOOL
  206. assoccmp(ap1, ap2)
  207.     ASSOC *ap1, *ap2;
  208. {
  209.     ASSOCELEM **table1;
  210.     ASSOCELEM *ep1;
  211.     ASSOCELEM *ep2;
  212.     long size1;
  213.     long size2;
  214.     HASH hash;
  215.     long dim;
  216.  
  217.     if (ap1 == ap2)
  218.         return FALSE;
  219.     if (ap1->a_count != ap2->a_count)
  220.         return TRUE;
  221.  
  222.     table1 = ap1->a_table;
  223.     size1 = ap1->a_size;
  224.     size2 = ap2->a_size;
  225.     while (size1-- > 0) {
  226.         for (ep1 = *table1++; ep1; ep1 = ep1->e_next) {
  227.             hash = ep1->e_hash;
  228.             dim = ep1->e_dim;
  229.             for (ep2 = ap2->a_table[hash % size2]; ;
  230.                 ep2 = ep2->e_next)
  231.             {
  232.                 if (ep2 == NULL)
  233.                     return TRUE;
  234.                 if (ep2->e_hash != hash)
  235.                     continue;
  236.                 if (ep2->e_dim != dim)
  237.                     continue;
  238.                 if (compareindices(ep1->e_indices,
  239.                     ep2->e_indices, dim))
  240.                         break;
  241.             }
  242.             if (comparevalue(&ep1->e_value, &ep2->e_value))
  243.                 return TRUE;
  244.         }
  245.     }
  246.     return FALSE;
  247. }
  248.  
  249.  
  250. /*
  251.  * Copy an association value.
  252.  */
  253. ASSOC *
  254. assoccopy(oldap)
  255.     ASSOC *oldap;
  256. {
  257.     ASSOC *ap;
  258.     ASSOCELEM *oldep;
  259.     ASSOCELEM *ep;
  260.     ASSOCELEM **listhead;
  261.     int oldhi;
  262.     int i;
  263.  
  264.     ap = assocalloc(oldap->a_count / CHAINLENGTH);
  265.     ap->a_count = oldap->a_count;
  266.  
  267.     for (oldhi = 0; oldhi < oldap->a_size; oldhi++) {
  268.         for (oldep = oldap->a_table[oldhi]; oldep;
  269.             oldep = oldep->e_next)
  270.         {
  271.             ep = (ASSOCELEM *) malloc(ELEMSIZE(oldep->e_dim));
  272.             if (ep == NULL)
  273.                 math_error("Cannot allocate association element");
  274.             ep->e_dim = oldep->e_dim;
  275.             ep->e_hash = oldep->e_hash;
  276.             ep->e_value.v_type = V_NULL;
  277.             for (i = 0; i < ep->e_dim; i++)
  278.                 copyvalue(&oldep->e_indices[i], &ep->e_indices[i]);
  279.             copyvalue(&oldep->e_value, &ep->e_value);
  280.             listhead = &ap->a_table[ep->e_hash % ap->a_size];
  281.             ep->e_next = *listhead;
  282.             *listhead = ep;
  283.         }
  284.     }
  285.     return ap;
  286. }
  287.  
  288.  
  289. /*
  290.  * Resize the hash table for an association to be the specified size.
  291.  * This is only actually done if the growth from the previous size is
  292.  * enough to make this worthwhile.
  293.  */
  294. static void
  295. resize(ap, newsize)
  296.     ASSOC *ap;
  297.     long newsize;
  298. {
  299.     ASSOCELEM **oldtable;
  300.     ASSOCELEM **newtable;
  301.     ASSOCELEM **oldlist;
  302.     ASSOCELEM **newlist;
  303.     ASSOCELEM *ep;
  304.     int i;
  305.  
  306.     if (newsize < ap->a_size + GROWHASHSIZE)
  307.         return;
  308.  
  309.     newsize = nextprime(newsize);
  310.     newtable = (ASSOCELEM **) malloc(sizeof(ASSOCELEM *) * newsize);
  311.     if (newtable == NULL)
  312.         math_error("No memory to grow association");
  313.     for (i = 0; i < newsize; i++)
  314.         newtable[i] = NULL;
  315.  
  316.     oldtable = ap->a_table;
  317.     oldlist = oldtable;
  318.     for (i = 0; i < ap->a_size; i++) {
  319.         while (*oldlist) {
  320.             ep = *oldlist;
  321.             *oldlist = ep->e_next;
  322.             newlist = &newtable[ep->e_hash % newsize];
  323.             ep->e_next = *newlist;
  324.             *newlist = ep;
  325.         }
  326.         oldlist++;
  327.     }
  328.  
  329.     ap->a_table = newtable;
  330.     ap->a_size = newsize;
  331.     free((char *) oldtable);
  332. }
  333.  
  334.  
  335. /*
  336.  * Free an association element, along with any contained values.
  337.  */
  338. static void
  339. assoc_elemfree(ep)
  340.     ASSOCELEM *ep;
  341. {
  342.     int i;
  343.  
  344.     for (i = 0; i < ep->e_dim; i++)
  345.         freevalue(&ep->e_indices[i]);
  346.     freevalue(&ep->e_value);
  347.     ep->e_dim = 0;
  348.     ep->e_next = NULL;
  349.     free((char *) ep);
  350. }
  351.  
  352.  
  353. /*
  354.  * Allocate a new association value with an initial hash table.
  355.  * The hash table size is set at specified (but at least a minimum size).
  356.  */
  357. ASSOC *
  358. assocalloc(initsize)
  359.     long initsize;
  360. {
  361.     register ASSOC *ap;
  362.     int i;
  363.  
  364.     if (initsize < MINHASHSIZE)
  365.         initsize = MINHASHSIZE;
  366.     ap = (ASSOC *) malloc(sizeof(ASSOC));
  367.     if (ap == NULL)
  368.         math_error("No memory for association");
  369.     ap->a_count = 0;
  370.     ap->a_size = initsize;
  371.     ap->a_table = (ASSOCELEM **) malloc(sizeof(ASSOCELEM *) * initsize);
  372.     if (ap->a_table == NULL) {
  373.         free((char *) ap);
  374.         math_error("No memory for association");
  375.     }
  376.     for (i = 0; i < initsize; i++)
  377.         ap->a_table[i] = NULL;
  378.     return ap;
  379. }
  380.  
  381.  
  382. /*
  383.  * Free an association value, along with all of its elements.
  384.  */
  385. void
  386. assocfree(ap)
  387.     register ASSOC *ap;
  388. {
  389.     ASSOCELEM **listhead;
  390.     ASSOCELEM *ep;
  391.     ASSOCELEM *nextep;
  392.     int i;
  393.  
  394.     listhead = ap->a_table;
  395.     for (i = 0; i < ap->a_size; i++) {
  396.         nextep = *listhead;
  397.         *listhead = NULL;
  398.         while (nextep) {
  399.             ep = nextep;
  400.             nextep = ep->e_next;
  401.             assoc_elemfree(ep);
  402.         }
  403.         listhead++;
  404.     }
  405.     free((char *) ap->a_table);
  406.     ap->a_table = NULL;
  407.     free((char *) ap);
  408. }
  409.  
  410.  
  411. /*
  412.  * Print out an association along with the specified number of
  413.  * its elements.  The elements are printed out in shortened form.
  414.  */
  415. void
  416. assocprint(ap, max_print)
  417.     ASSOC *ap;
  418.     long max_print;
  419. {
  420.     ASSOCELEM *ep;
  421.     long index;
  422.     long i;
  423.     int savemode;
  424.  
  425.     if (max_print <= 0) {
  426.         math_fmt("assoc (%ld element%s)", ap->a_count,
  427.             ((ap->a_count == 1) ? "" : "s"));
  428.         return;
  429.     }
  430.     math_fmt("\n  assoc (%ld element%s):\n", ap->a_count,
  431.         ((ap->a_count == 1) ? "" : "s"));
  432.  
  433.     for (index = 0; ((index < max_print) && (index < ap->a_count));
  434.         index++)
  435.     {
  436.         ep = elemindex(ap, index);
  437.         if (ep == NULL)
  438.             continue;
  439.         math_str("  [");
  440.         for (i = 0; i < ep->e_dim; i++) {
  441.             if (i)
  442.                 math_chr(',');
  443.             savemode = math_setmode(MODE_FRAC);
  444.             printvalue(&ep->e_indices[i],
  445.                 (PRINT_SHORT | PRINT_UNAMBIG));
  446.             math_setmode(savemode);
  447.         }
  448.         math_str("] = ");
  449.         printvalue(&ep->e_value, PRINT_SHORT | PRINT_UNAMBIG);
  450.         math_chr('\n');
  451.     }
  452.     if (max_print < ap->a_count)
  453.         math_str("  ...\n");
  454. }
  455.  
  456.  
  457. /*
  458.  * Return a trivial hash value for an association.
  459.  */
  460. HASH
  461. assochash(ap)
  462.     ASSOC *ap;
  463. {
  464.     return ap->a_count * 700001;
  465. }
  466.  
  467.  
  468. /*
  469.  * Compare two lists of index values to see if they are identical.
  470.  * Returns TRUE if they are the same.
  471.  */
  472. static BOOL
  473. compareindices(v1, v2, dim)
  474.     VALUE *v1;
  475.     VALUE *v2;
  476.     long dim;
  477. {
  478.     int i;
  479.  
  480.     for (i = 0; i < dim; i++)
  481.         if (v1[i].v_type != v2[i].v_type)
  482.             return FALSE;
  483.  
  484.     while (dim-- > 0)
  485.         if (comparevalue(v1++, v2++))
  486.             return FALSE;
  487.  
  488.     return TRUE;
  489. }
  490.  
  491.  
  492. /*
  493.  * Return the next prime number up from the specified value.
  494.  * This is used to pick a good hash table size.
  495.  */
  496. static long
  497. nextprime(n)
  498.     long n;
  499. {
  500.     long i;
  501.  
  502.     if ((n & 0x01) == 0)
  503.         n++;
  504.     while (TRUE) {
  505.         for (i = 3; n % i; i += 2) {
  506.             if (i * i > n)
  507.                 return n;
  508.         }
  509.         n += 2;
  510.     }
  511. }
  512.  
  513. /* END CODE */
  514.